
def kmp_match(text, pattern):
    # 构建最长合适前缀数组
    longest_prefix = [0] * len(pattern)
    print(longest_prefix)
    build_longest_prefix(pattern, longest_prefix)
    print(longest_prefix)
    # 进行模式匹配
    i = 0  # text中的指针
    j = 0  # pattern中的指针

    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1

            if j == len(pattern):
                # 匹配成功，返回第一个匹配的位置
                return i - j

        elif j > 0:
            # 发生不匹配，回溯到最长合适前缀的末尾
            j = longest_prefix[j - 1]
        else:
            # 发生不匹配，继续在text中移动指针
            i += 1

    return -1  # 未找到匹配的模式


def build_longest_prefix(pattern, longest_prefix):
    length = 0  # 最长合适前缀的长度
    i = 1

    n = 1
    while i < len(pattern):
        n+=1
        print(i,length)
        print(pattern[i],pattern[length])
        if pattern[i] == pattern[length]:
            length += 1
            longest_prefix[i] = length
            i += 1
        else:
            if length != 0:
                # 回溯到前一个合适前缀的末尾
                length = longest_prefix[length - 1]
            else:
                # 没有找到合适前缀
                longest_prefix[i] = 0
                i += 1
    print(n)

# 测试代码
text = "ABABDABACDABABCABAB"
pattern = "ababefgaba"
result = kmp_match(text, pattern)
print(result)
